#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int kmp_find(const char *target, const char *pattern);

int main()
{
    char source[] = "annbcdaannacannanannabnna";
    char pattern[] = "annacanna";

    printf("result is : %d\n", kmp_find(source, pattern));

    return 0;
}



int kmp_find(const char *target, const char *pattern )
{

    int     target_length = strlen(target);
    int     pattern_length = strlen(pattern);

    int     *overlay_value = (int *)malloc(pattern_length * sizeof(int));
    int     index = 0;
    int     i;
    overlay_value[0] = -1;

    for (i = 1; i < pattern_length; i++) {
        index = overlay_value[i - 1];

        while(index >= 0 && pattern[index + 1] != pattern[i]) {
            index = overlay_value[index];
        }

        if (pattern[index + 1] == pattern[i]){
            overlay_value[i] = index + 1;
        }
        else {
            overlay_value[i] = -1;
        }
    }

    //match algorithm starting!

    int     pattern_index = 0;
    int     target_index = 0;

    while (pattern_index < pattern_length && target_index < target_length) {
        if (target[target_index] == pattern[pattern_index]) {
            target_index++;
            pattern_index++;
        } else if (pattern_index == 0) {
            target_index++;
        } else {
            pattern_index = overlay_value[pattern_index - 1] + 1;
        }
    }

    if (pattern_index == pattern_length)
        return target_index - pattern_index;
    else
        return -1;



    return 0;
}


void get_nextval(char const* ptrn, int plen, int* nextval)    
{    
    int i = 0;     
    nextval[i] = -1;    
    int j = -1;    
    while( i < plen-1 )    
    {    
        if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分    
        {    
            ++i;    
            ++j;    
            //修正的地方就发生下面这4行    
            if( ptrn[i] != ptrn[j] ) //++i，++j之后，再次判断ptrn[i]与ptrn[j]的关系    
                nextval[i] = j;      //之前的错误解法就在于整个判断只有这一句。    
            else    
                nextval[i] = nextval[j];    
        }    
        else                                 //循环的else部分    
            j = nextval[j];    
    }    
}    



int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)    
{    
    int i = pos;    
    int j = 0;    
    while ( i < slen && j < plen )    
    {    
        if( j == -1 || src[i] == patn[j] )    
        {    
            ++i;    
            ++j;    
        }    
        else    
        {    
            j = nextval[j];              
            //当匹配失败的时候直接用p[j_next]与s[i]比较，    
            //下面阐述怎么求这个值，即匹配失效后下一次匹配的位置    
        }    
    }    
    if( j >= plen )    
        return i-plen;    
    else    
        return -1;    
}    